#include <cstring>
#include <vector>

using namespace std;

/**
 * @方法: 递归写法
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
int* memo;

int dp(vector<int>& coins, int amount) {
    if (amount < 0) return -1;
    if(memo[amount] != -666) return memo[amount];
    if(amount == 0) {
        memo[amount] = 0;
        return 0;
    }
    int res = 0x3f3f3f3f;
    for(int coin:coins){
        int sub = dp(coins, amount-coin);
        if(sub == -1) continue;
        res = min(res, 1+sub);
    }
    memo[amount] = (res == 0x3f3f3f3f) ? -1 : res;
    return (res == 0x3f3f3f3f) ? -1 : res;
}

int coinChange(vector<int>& coins, int amount) {
    memo = new int[amount+1];
    for(int i=0;i<amount+1;i++){
        // 尚未被计算
        memo[i] = -666;
    }
    return dp(coins, amount);
}


/**
 * @方法: 迭代写法
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
int coinChange(vector<int>& coins, int amount) {
    int dp[amount + 1];
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < amount + 1; i++) {
        for (int coin : coins) {
            if (coin > i) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == 0x3f3f3f3f) ? -1 : dp[amount];
}